home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / lib / calc / pollard.cal < prev    next >
Text File  |  1995-07-17  |  620b  |  36 lines
  1. /*
  2.  * Copyright (c) 1993 David I. Bell
  3.  * Permission is granted to use, distribute, or modify this source,
  4.  * provided that this copyright notice remains intact.
  5.  *
  6.  * Factor using Pollard's p-1 method.
  7.  */
  8.  
  9. define factor(N, B, ai, af)
  10. {
  11.     local    a, k, i, d;
  12.  
  13.     if (isnull(B))
  14.         B = 1000;
  15.     if (isnull(ai))
  16.         ai = 2;
  17.     if (isnull(af))
  18.         af = ai + 20;
  19.     k = lcmfact(B);
  20.     d = lfactor(N, B);
  21.     if (d > 1)
  22.         return d;
  23.     for (a = ai; a <= af; a++) {
  24.         i = pmod(a, k, N);
  25.         d = gcd(i - 1, N);
  26.         if ((d > 1) && (d != N))
  27.             return d;
  28.     }
  29.     return 1;
  30. }
  31.  
  32. global lib_debug;
  33. if (lib_debug >= 0) {
  34.     print "factor(N, B, ai, af) defined";
  35. }
  36.